package org.example.myleet.p528;

/**
 * 思路：
 * 可以计算出每个下标的权重（概率），按照下标的顺序累加这些概率，得到累积概率的前缀和
 * 这个前缀和就像光谱一样，每个下标的概率都占据了一个范围
 * 0|0.25(0~0.25)|0.75(0.25~1.0)|1.0
 * 这个累积概率的前缀和还有个好处，就是随着下标增大，其累积概率是单调增大的，因此对于这种有序的数组可以用二分法以log(n)的复杂度查找到目标
 * pickIndex被调用时，就像掷骰子一样掷出一个随机小数（0～1之间），然后用二分法找一下这个小数在哪个区间中，输出对应的下标就可以了
 */
public class Solution {

    //记录w的长度
    private int n;

    //记录累积概率前缀和
    private double[] freqSum;

    public Solution(int[] w) {
        n = w.length;
        freqSum = new double[n + 1];
        freqSum[0] = 0;
        double total = 0;
        for (int weight : w) {
            //先计算w中所有的和
            total += weight;
        }
        for (int i = 0; i < n; ++i) {
            //再计算每个位置的累积概率前缀和
            freqSum[i + 1] = freqSum[i] + w[i] / total;
        }
    }

    public int pickIndex() {
        double rand = Math.random();
        int l = 0, r = n, m;
        while (r - l > 1) {
            m = (l + r) / 2;
            if (freqSum[m] > rand) {
                r = m;
            } else if (freqSum[m] < rand) {
                l = m;
            } else {
                if (m == 0) {
                    return 0;
                }
                return m - 1;
            }
        }
        return l;
    }
}
